using UnityEngine;
using System.Collections.Generic;
using System.Linq;

public class PoissonDiskSampling
{
    public static List<Vector2> GeneratePoints(float radius, Bounds bounds, int numPoints, int rejectionSamples,
        System.Func<Vector2, bool> isValidPosition)
    {
        // 计算单元格大小
        float cellSize = radius / Mathf.Sqrt(2);

        // 确定网格尺寸
        int gridWidth = Mathf.CeilToInt(bounds.size.x / cellSize);
        int gridHeight = Mathf.CeilToInt(bounds.size.y / cellSize);

        // 创建网格
        Vector2?[,] grid = new Vector2?[gridWidth, gridHeight];
        List<Vector2> activeList = new List<Vector2>();
        List<Vector2> points = new List<Vector2>();

        // 第一个点
        Vector2 firstPoint = new Vector2(
            Random.Range(bounds.min.x, bounds.max.x),
            Random.Range(bounds.min.y, bounds.max.y)
        );

        if (isValidPosition(firstPoint))
        {
            AddPoint(firstPoint);
        }
        else
        {
            // 如果第一个点无效，尝试找到有效点
            bool found = false;
            for (int i = 0; i < rejectionSamples && !found; i++)
            {
                firstPoint = new Vector2(
                    Random.Range(bounds.min.x, bounds.max.x),
                    Random.Range(bounds.min.y, bounds.max.y)
                );
                if (isValidPosition(firstPoint))
                {
                    AddPoint(firstPoint);
                    found = true;
                }
            }

            if (!found) return points; // 无法找到有效点
        }

        while (activeList.Count > 0 && points.Count < numPoints)
        {
            // 随机选择一个活动点
            int randomIndex = Random.Range(0, activeList.Count);
            Vector2 point = activeList[randomIndex];
            bool found = false;

            // 尝试生成新点
            for (int i = 0; i < rejectionSamples; i++)
            {
                // 在环形区域内生成随机点
                float angle = Random.Range(0, 2 * Mathf.PI);
                float distance = Random.Range(radius, 2 * radius);
                Vector2 newPoint = point + new Vector2(
                    Mathf.Cos(angle) * distance,
                    Mathf.Sin(angle) * distance
                );

                // 检查新点是否有效
                if (IsValid(newPoint, bounds, cellSize, radius, grid, isValidPosition))
                {
                    AddPoint(newPoint);
                    found = true;
                    break;
                }
            }

            // 如果没有找到有效点，从活动列表中移除
            if (!found)
            {
                activeList.RemoveAt(randomIndex);
            }
        }

        return points;

        // 添加点到所有数据结构中
        void AddPoint(Vector2 point)
        {
            points.Add(point);
            activeList.Add(point);
            int gridX = Mathf.FloorToInt((point.x - bounds.min.x) / cellSize);
            int gridY = Mathf.FloorToInt((point.y - bounds.min.y) / cellSize);
            grid[gridX, gridY] = point;
        }

        // 检查点是否有效
        bool IsValid(Vector2 point, Bounds bounds, float cellSize, float radius, Vector2?[,] grid,
            System.Func<Vector2, bool> isValidPosition)
        {
            // 检查是否在边界内
            if (!bounds.Contains(point)) return false;

            // 检查是否在有效区域内
            if (!isValidPosition(point)) return false;

            // 检查邻近单元格
            int gridX = Mathf.FloorToInt((point.x - bounds.min.x) / cellSize);
            int gridY = Mathf.FloorToInt((point.y - bounds.min.y) / cellSize);

            int startX = Mathf.Max(0, gridX - 2);
            int endX = Mathf.Min(grid.GetLength(0) - 1, gridX + 2);
            int startY = Mathf.Max(0, gridY - 2);
            int endY = Mathf.Min(grid.GetLength(1) - 1, gridY + 2);

            for (int x = startX; x <= endX; x++)
            {
                for (int y = startY; y <= endY; y++)
                {
                    if (grid[x, y].HasValue)
                    {
                        float sqrDist = (point - grid[x, y].Value).sqrMagnitude;
                        if (sqrDist < radius * radius)
                        {
                            return false;
                        }
                    }
                }
            }

            return true;
        }
    }
}

public class SpawnBallsWithPoissonDisk : MonoBehaviour
{
    public GameObject ballPrefab;
    public EdgeCollider2D edgeCollider;
    public float ballRadius = 0.5f;
    public int numberOfBalls = 10;
    public int rejectionSamples = 30;

    void Start()
    {
        SpawnBalls();
    }

    void SpawnBalls()
    {
        List<Vector2> points = PoissonDiskSampling.GeneratePoints(
            ballRadius * 2, // 两倍半径确保球体不重叠
            edgeCollider.bounds,
            numberOfBalls,
            rejectionSamples,
            pos => IsInsideEdgeCollider(pos)
        );

        foreach (Vector2 point in points)
        {
            Instantiate(ballPrefab, new Vector3(point.x, point.y, 0), Quaternion.identity, transform);
        }
    }

    bool IsInsideEdgeCollider(Vector2 point)
    {
        // 使用多边形碰撞检测
        return PointInPolygon(point, edgeCollider.points);
    }

    // 射线法判断点是否在多边形内
    bool PointInPolygon(Vector2 point, Vector2[] polygon)
    {
        int polygonLength = polygon.Length;
        bool inside = false;

        // 需要将局部坐标转换为世界坐标
        Vector3[] worldPoints = polygon.Select(p => transform.TransformPoint(p)).ToArray();

        Vector2 p1, p2;

        Vector2 oldPoint = worldPoints[polygonLength - 1];

        for (int i = 0; i < polygonLength; i++)
        {
            Vector2 newPoint = worldPoints[i];

            if (newPoint.x > oldPoint.x)
            {
                p1 = oldPoint;
                p2 = newPoint;
            }
            else
            {
                p1 = newPoint;
                p2 = oldPoint;
            }

            if ((newPoint.x < point.x) == (point.x <= oldPoint.x) &&
                (point.y - p1.y) * (p2.x - p1.x) < (p2.y - p1.y) * (point.x - p1.x))
            {
                inside = !inside;
            }

            oldPoint = newPoint;
        }

        return inside;
    }
}
